The function of traffic management is to control the use of network resources, optimizing network utilization and avoiding bottlenecks in the network. Various devices interfacing a network send and receive data on link connections. One important function in the high speed networks is to control the rate at which the data are delivered over the links.
In the so-called Asynchronous Transfer Mode (ATM) Networks the data are called ATM cells and transit over physical links in the network from endpoints to endpoints through internal nodes (also called switches) which route the cells to their destination endpoint. The cells within either a endpoint or a node are temporarily stored before being admitted on a link. Among the different parameters determining which one and the moment at which a new cell is to be output, the current cell rate (CCR) is mandatory. The computation of this parameter which is also expressed as a delay (the inter-cell delay) includes the step of performing a division.
Since the division belongs to an interactive process, the duration of this operation must be minimized. There are several families of dividers: dividers using iterations, dividers using logarithms and fully combinatorial dividers.
The dividers using iteration perform the operation thanks to a succession of subtractions and shift operations. These circuits generate the exact value of the division but they require several cycles to compute the result. The number of steps necessary to compute the result equals the number of bits of the divisor operand. These circuits are too slow for high speed network applications.
The dividers using logarithms require very large memory tables. This type of circuits are resources consuming.
The fully combinatorial dividers circuits require expensive circuitry. Moreover this type of circuits is not adapted to the high speed networks because they are not fast enough.
Another known combinational approach is based on a process using the so-called non restoring array divider as defined by H. H. Guild in "Some Cellular Logic Arrays for Non restoring Binary Division" the Radio and Elect. Engr., Vol. 39 June 1970, using controlled Adder/Subtracter cells. Such technique is hardware consuming and is sized to a precise shape of dividend/divisor, say a 32 bits/16 bits or any combination of (2 n bits/n bits).
The general state of the prior art with respect to solving the aforementioned division problem may be best illustrated and understood with reference to the several patents to be described immediately hereinafter.
U.S. Pat. No. 4,228,518 from Chamberlin discloses a microprocessor having the capability of performing either a multiply or divide operation from a single instruction for each operation. Standard circuitry of a microprocessor is used along with a multiply/divide cycle counter, logic circuitry, and a shift network separate from the arithmetic logic unit. The microprocessor has the capability of performing unsigned integer multiplication and division. A shift and add algorithm is used for multiplication while for division a non-restoring divide algorithm is used. While this circuit does not occupy a great amount of additional circuitry on the microprocessor, several cycles of operation are needed to complete the division.
U.S. Pat. No. 4,707,798 from Nakano discloses a divide method and a divide apparatus for use in a data processing system by employing interpolation approximation. The divisor and the dividend are normalized in a normalization circuit. A table unit stores a plurality of approximate reciprocal divisors and differences between adjacent approximate reciprocal divisors and is addressed by the high-order bits of the normalized divisor. The approximate reciprocal divisor read out from the table unit is, in an interpolation approximation circuit, changed into an interpolation approximated approximate reciprocal divisor in accordance with a plurality of bits following the high-order bits and the difference. A multiplication unit multiplies the interpolation approximated approximate reciprocal divisor by the normalized dividend to obtain through successive iterations a quotient.
U.S. Pat. No. 5,068,816 from Noetzel discloses a function evaluator which uses an interpolating memory for evaluating functions. An argument is expressed in digital bits. High order bits are used to address a memory for selecting coefficients. Low order bits are used in combinational logic to supply powers which multiply the coefficients. An adder sums the products of the multipliers, and the summation is the function evaluation. This solution is hardware consuming because the apparatus is not limited to the division. The correction factor value is important due to the fact that the segments have all the same size, as will be explained later in the description.
The main characteristics of the prior art solutions are that a precise result of the division is sought which need several cycles of operations in order to apply corrections to an estimated result.
Therefore the circuits of these references are not acceptable for the present applications of very high speed networks in which the main constraint is the delay and not the accuracy.
Accordingly, it would be desirable to be able to provide a new method and system to evaluate an approximation of a division which eliminates the aforementioned constraint of delay and complexity of present solutions.